import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Jiang Jinxi
 * Date: 2024-03-23
 * Time: 19:29
 */
public class Sort {
    public static void insertSort(int[] arr){
        for (int i = 1; i <arr.length ; i++) {
            int tmp = arr[i];
            int j = i-1;
            for ( ; j >= 0; j--) {
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    //arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

    public static void shellSort(int[] arr){
        int gap = arr.length/2;
        while(gap!= 1){
            gap = gap/2;
            shell(arr, gap);
        }
    }
    private static void shell(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j>=0; j-=gap) {
                if(arr[j] > tmp){
                    arr[j+gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    public static void selectSort1(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }
    public static void selectSort2(int[] arr){
        int left = 0;
        int right = arr.length -1;
       while(left< right){
           for (int i = left; i <= right ; i++) {
               int minIndex = left;
               int maxIndex = right;
               if(arr[i] < arr[minIndex]){
                 minIndex = i;
               }
               if(arr[i] > arr[maxIndex]){
                  maxIndex = i;
               }
               swap(arr,left,minIndex);
               swap(arr,right,maxIndex);
               left++;
               right--;
           }
       }
    }
    private static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void heapSort(int[] arr){
        createHeap(arr);
        int end = arr.length-1;
        while(end > 0){
            swap(arr,0,end);
            siftDown(arr,0,end);
            end--;
        }
    }
    private static void createHeap(int[] arr){
        for(int parent = (arr.length-1-1)/2;parent >0;parent--){
            siftDown(arr,parent,arr.length);
        }
    }
    private static void siftDown(int[] arr, int parent, int len){
        int child = (parent*2)+1;
        while(child < len){
            if(child +1 < len && arr[child+1]>arr[child]){
                child = child+1;
            }
            if(arr[child] > arr[parent]){
                swap(arr,child,parent);
                parent = child;
                child = (parent*2)+1;
            }else{
                break;
            }
        }
    }

    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            int flag = 0;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag = 1;
                }
            }
            if(flag == 0){
                return;
            }
        }
    }

    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }
    private static void quick(int[] arr,int left,int right){
        if(left >= right){
            return ;
        }
        //优化1
        int index = middleNum(arr,left,right);
        swap(arr,index,left);

        //优化2
        if(right-left+1 <= 10 ){
            insertSort2(arr,left,right);
            return;
        }

        int pivot = partition(arr,left,right);
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    public static void insertSort2(int[] arr,int left,int right){
        for (int i = 1 + left; i <=right ; i++) {
            int tmp = arr[i];
            int j = i-1;
            for ( ; j >= 0; j--) {
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    //arr[j+1] = tmp;
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }
    private static int partitionHoare(int[] arr,int left,int right){
        int i = left;
        int j = right;
        int pivot = left;
        while(i < j){
            while(i < j && arr[j] >= arr[pivot]){
                j--;
            }
            while(i < j && arr[i] <= arr[pivot]){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,pivot);
        return i;
    }

    private static int partition(int[] arr,int left,int right){
        int i = left;
        int j = right;
        int pivot = arr[left];
        while(i < j){
            while(i<j && arr[j] >= pivot){
                j--;
            }
            arr[i] = arr[j];
            while(i<j && arr[i] < pivot){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }

    private static int middleNum(int[] arr,int left,int right){
        int mid = left + ((right-left)>>1);
        if (arr[left] < arr[right]){
            if(arr[mid] < arr[left]){
                return left;
            }else if(arr[mid] > arr[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(arr[mid] < arr[right]){
                return right;
            }else if(arr[mid] > arr[left]){
                return left;
            }else{
                return mid;
            }

        }
    }

    public static void quickSortNorR(int[] arr){
        int left = 0;
        int right = arr.length-1;
        int pivot = partition(arr,left,right);
        Stack<Integer> stack = new Stack<>();
        if(pivot - 1 > left){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if(pivot + 1 < right){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(arr,left,right);
            if(pivot - 1 > left){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot + 1 < right){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    public static void mergeSort(int[] arr){
        mergeFunc(arr,0,arr.length-1);
    }
    private static void mergeFunc(int[] arr,int left,int right){
        if(left >= right){
            return ;
        }
        int mid = left+((right-left)>>1);
        mergeFunc(arr,left,mid);
        mergeFunc(arr,mid+1,right);

        merge(arr,left,mid,right);
    }
    private static void merge(int[] arr, int left,int mid,int right){
        int s1 = left;
        int s2 = mid +1;
        int e1 = mid;
        int e2 = right;
        int[] tmpArr = new int[right-left+1];
        int k = 0;
        while(s1 <= e1 && s2 <= e2){
            if(arr[s1] > arr[s2]){
                tmpArr[k++] = arr[s2++];
            }else{
                tmpArr[k++] = arr[s1++];
            }
        }
        while(s1 <= e1){
            tmpArr[k++] = arr[s1++];
        }
        while(s2 <= e2){
            tmpArr[k++] = arr[s2++];
        }

        for (int i = 0; i < k; i++) {
            arr[i+left] = tmpArr[i];

        }
    }
    public static void mergeSortNorR(int[] arr){
        int gap = 1;
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i=i+2*gap) {
                int left = i;
                int mid = left + gap -1;
                if(mid >= arr.length){
                    mid = arr.length-1;
                }
                int right = mid +gap;
                if(right >= arr.length){
                    right = arr.length-1;
                }
                merge(arr,left,mid,right);
            }
            gap *= 2;
        }
    }
}
